#!/usr/bin/php
<?PHP

define("ROW", 10);
define("COL", 20);

function show($map)
{
    echo "\033[1;1H";
    foreach ($map as $row)
    {
        for ($i = 0; $i < COL; ++$i) {
            echo $row[$i];
        }
        echo PHP_EOL;
    }
}

function getxy($map, $ch)
{
    foreach ($map as $r => $row) {
        for ($i = 0; $i < COL; ++$i) {
            if ($row[$i] == $ch)
                return array('r' => $r, 'c' => $i);
        }
    }
    return null;
}

/*
function maze(& $map, & $direct, $cur, & $end)
{
    usleep(100000);
    $map[$cur['r']][$cur['c']] = '@';
    show($map);

    if ($cur == $end)
        exit(0);

    for ($i = 0; $i < 4; ++$i) {
        $new['r'] = $cur['r'] + $direct[$i]['r'];
        $new['c'] = $cur['c'] + $direct[$i]['c'];

        $ch = $map[$new['r']][$new['c']];

        if ($ch == '@' || $ch == '#')
            continue;

        maze($map, $direct, $new, $end);
    }
    usleep(100000);
    $map[$cur['r']][$cur['c']] = ' ';
    show($map);
}
 */

function maze(& $map, & $direct, $cur, & $end)
{
    $stack = array();
START:
    usleep(100000);
    $map[$cur['r']][$cur['c']] = '@';
    show($map);

    if ($cur == $end)
        return;

    $i = 0;
I:
    // printf("\033[s\033[12;1Hi = %d\033[u", $i);
    while ($i < 4) {
        $new['r'] = $cur['r'] + $direct[$i]['r'];
        $new['c'] = $cur['c'] + $direct[$i]['c'];

        $ch = $map[$new['r']][$new['c']];

        ++$i;

        if ($ch == '@' || $ch == '#')
            continue;

        // maze($map, $direct, $new, $end);
        $stack[] = array($cur, $i); //模拟函数压栈
        $cur = $new;   //模拟函数传参
        goto START;     //模拟函数调用
    }
    usleep(100000);
    $map[$cur['r']][$cur['c']] = ' ';
    show($map);

    //模拟函数出栈
    list($cur, $i) = array_pop($stack);
    printf("\033[s\033[12;1Hi = %d\033[u", $i);
    goto I;
}

function main()
{
    $map = [
        "####################",
        "#        S #       #",
        "# # ##### ## ##### #",
        "# # # # # ## #   # #",
        "# # # # #    # #   #",
        "# # # # # # ## #####",
        "# #   # # #  ##    #",
        "# ##### # ##    ## #",
        "#       # ######E  #",
        "####################"
    ];
    $direct = [
        ['r' => 0, 'c' => 1],
        ['r' => 0, 'c' => -1],
        ['r' => 1, 'c' => 0],
        ['r' => -1, 'c' => 0]
    ];

    $start = getxy($map, 'S');
    $end = getxy($map, 'E');
    $stack = array($start);

    echo "\033[2J";
    show($map);

    // maze($map, $direct, $start, $end);
    // return 0;

    while (TRUE)
    {
        $cur = array_pop($stack);
        // $cur = array_shift($stack);
        // fgets(STDIN);
        usleep(100000);
        $map[$cur['r']][$cur['c']] = '@';
        show($map);

        if ($cur === $end)
            break;

        for ($i = 0; $i < 4; ++$i) {
            $new['r'] = $cur['r'] + $direct[$i]['r'];
            $new['c'] = $cur['c'] + $direct[$i]['c'];

            $ch = $map[$new['r']][$new['c']];

            if ($ch == '@' || $ch == '#')
                continue;

            $stack[] = $new;
        }
    }

    return 0;
}

exit(main());


